• Testing empirical performance of a variety of bandit algorithms, both contextless and contextful
• Using the Yahoo! Webscope Today Module data [11], which covers 10 days of article recommendation data on the Yahoo! homepage
• Building heavily on Li, Chu et al 2011, which uses this dataset to create an unbiased estimator for bandit algorithm performance [7]
  • Main contribution in further investigating characteristics of the specific dataset, and running far more algorithms on it
  • May also clean up implementations of algorithms and post publicly (hard to find actual code)

• Bandit algorithms are not as well empirically tested / benchmarked as most other areas of statistical learning–most current empirical tests are simulations or toy problems [2, 5]
  • Simulations are subject to bias, and obviously work well when underlying distribution matches that used by algorithm
  • Toy problems don't capture complexity of real-world problems
• Hard to find good benchmarks, since we can't see dataset counterfactuals (off-policy problem). We almost require online problems [7, 9]
• Yahoo! Today claims to be the first solid benchmark

• 45,811,883 distinct visit events over 10 days in 2009
• 271 articles observed within the course of the 10 days
• User is shown an article in the feature box
• Pool of articles is non-constant and can change (varies from 19 to 25)
• Users and articles have 5 features based on conjoint analysis (and one constant feature)
• Reward for our bandit algorithms, and primary evaluation metric, will be article clicks and/or clickthrough rate

For algorithm/policy \(P\), each trial \(t\) to \(T\) trials:

1. Algorithm observes user \(u_t\) and a set of \(A_t\) arms (articles) together with context vector \(x_{t,a}\) for \(a \in A_t\). \(x_{t,a}\) contains features and interactions from both user \(u_t\) and arm \(a_t\). Specifically \(x_{t,a} = \mathbf{u} \mathbf{a}^T\) where \(\mathbf{u}\) is the feature vector for user \(u_t\) and \(\mathbf{a}\) is the feature vector for arm \(a_t\)
2. Based on \(A\)'s observations of rewards per arm for previous trial trials, \(P\) chooses arm from \(A_t\) and recieves payoff \(r_{t,a}\).
3. Algorithm updates strategy based on new observation. No feedback is received for unchosen arms.

• Policy estimator follows the same general principle
• Keep observations that fall within the distribution, else reject

• Evaluator is biased for cases where stream \(S\) of data is not finite (premature end)
• Lots of rejected data in order to get a desired \(T\). On average:
  • 220,000 data points to get 10,000 useable observations
  • 6.7 million data points to get 300,000 useable observations
  • 25 million data points to get 1 million useable observations
• In this case, limiting \(T\) to 1 million at most, which means \(S\) is effectively infinite
• Given \(K\) arms, we'd expect \(\frac{K-1}{K}\) discards [Li et al 2011]

• Features sum to one – and in general, one feature dominates each user
• If clusters are closely linked to different articles, contextual bandits should do better than context-less

• LinUCB and GLM-UCB would likely be even better than these results (not shown here, since these are all \(T = 1,000,000\))

##                Policy      CTR
## 1:             KL-UCB 0.054508
## 2:           Thompson 0.054392
## 3:                UCB 0.050476
## 4:         IndexedUCB 0.049134
## 5: ContextualThompson 0.041023
## 6:             Random 0.036651
## 7:             Random 0.036580
## 8: EpsilonGreedy(0.1) 0.035946

• Further evaluation on contextful algorithms against what they should have pulled for each user cluster
• Trying to get LinUCB and GLM-UCB running in some sort of reasonable time
• Why does contextual Thompson Sampling do so terribly (along with indexed UCB)?

• Empirical results are mostly what we expect and largely match past, simulation results [2, 4, 5]
• "Rejection sampling" is a good technique for evaluating various bandit algorithms
• Limited in some ways to web applications, due to high rejection rate, but will hopefully cause more interest in collecting this type of data